跳到主要内容

面试题 17.05. 字母与数字

· 阅读需 2 分钟

1、题干​

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。

返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例 1:

输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]

示例 2:

输入: ["A","A"]

输出: []

提示：

  • array.length <= 100000

2、思路​

  • 遍历数组 array 并计算前缀和 sum，遇到字母 sum+1 否则 sum-1
  • 如果当前 sum 的值从未出现过，将 sum 与下标 i 分别作为键值存入哈希表 map
  • 如果当前 sum 的值已出现过，则 [map.get(sum)+1,i+1) 区间的子数组作为备选答案
  • 最后取左下标最小的最长子数组

3、代码​

function findLongestSubarray(array: string[]): string[] {
    let sum = 0, l = 0, r = 0;
    const map = new Map([[0, -1]]);

    for (let i = 0; i < array.length; i++) {
        sum += (/[a-z]/i.test(array[i]) ? 1 : -1);
        const j = map.get(sum);

        if (j === undefined) map.set(sum, i);
        else if (i - j > r - l) r = i, l = j;
    }

    return array.slice(l + 1, r + 1);
};

4、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png